{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Height Tree LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #array #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #数组 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortedArrayToBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小高度树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。</p><strong>示例:</strong><pre>给定有序数组: [-10,-3,0,5,9],<br><br>一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：<br><br>          0 <br>         / &#92 <br>       -3   9 <br>       /   / <br>     -10  5 <br></pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-height-tree-lcci](https://leetcode.cn/problems/minimum-height-tree-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-height-tree-lcci](https://leetcode.cn/problems/minimum-height-tree-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        # 创建一棵高度最小的二叉搜索树 \n",
    "\n",
    "        # length = len(num)       # 二叉树的节点数 \n",
    "        # mid_length = length // 2\n",
    "        # # 是不是可以用递归创建二叉搜索树 ？\n",
    "\n",
    "        # def recur(left,right):\n",
    "        #     if left > right:\n",
    "        #         return \n",
    "        #     mid = (left + right) // 2\n",
    "        #     root = TreeNode(nums[mid])      # 创建根节点 \n",
    "        #     root.left = recur(left,mid-1)\n",
    "        #     recur(mid+1,right)\n",
    "\n",
    "        # recur(0,length-1)        # 根节点的下标值，左右指针\n",
    "\n",
    "        if not nums:\n",
    "            return \n",
    "        length = len(nums)\n",
    "        mid = length // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[0:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:length])\n",
    "\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        n=len(nums)\n",
    "        if n==0:\n",
    "            return None\n",
    "        if n==1:\n",
    "            root=TreeNode(nums[0])\n",
    "            return root\n",
    "        m=n//2\n",
    "        root=TreeNode(nums[m])\n",
    "        root.left=self.sortedArrayToBST(nums[:m])\n",
    "        root.right=self.sortedArrayToBST(nums[m+1:])\n",
    "        return root\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def buildTree(nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "            middle = len(nums)//2\n",
    "            root = TreeNode(nums[middle])\n",
    "            root.left = buildTree(nums[:middle])\n",
    "            root.right = buildTree(nums[middle+1:])\n",
    "            return root\n",
    "\n",
    "        return buildTree(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                return None\n",
    "            mid = (l + r) // 2\n",
    "            node = TreeNode(nums[mid])\n",
    "            node.left = dfs(l, mid - 1)\n",
    "            node.right = dfs(mid + 1, r)\n",
    "            return node\n",
    "        return dfs(0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def zhongxu(self,nums,left,right):\n",
    "        if left>right:\n",
    "            return None\n",
    "        mid=(left+right)//2\n",
    "        root=TreeNode(nums[mid])\n",
    "        root.left=self.zhongxu(nums,left,mid-1)\n",
    "        root.right=self.zhongxu(nums,mid+1,right)\n",
    "        return root\n",
    "        \n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        root=self.zhongxu(nums,0,len(nums)-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return \n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        n = len(nums)\n",
    "        if n <= 0:\n",
    "            return None\n",
    "        if n == 1:\n",
    "            return TreeNode(nums[0], None, None)\n",
    "        t = n // 2\n",
    "        return TreeNode(nums[t], self.sortedArrayToBST(nums[:t]), self.sortedArrayToBST(nums[1+t:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        index = len(nums) // 2\n",
    "        root = TreeNode(nums[index])\n",
    "        root.left = self.sortedArrayToBST(nums[:index])\n",
    "        root.right = self.sortedArrayToBST(nums[index+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid=len(nums)//2\n",
    "        root=TreeNode(nums[mid])\n",
    "        root.left=self.sortedArrayToBST(nums[:mid])\n",
    "        root.right=self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\tdef sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "\t\tle = len(nums)\n",
    "\t\tif le == 1:\n",
    "\t\t\troot_node = TreeNode(nums[0])\n",
    "\t\t\treturn root_node\n",
    "\t\telif le == 0:\n",
    "\t\t\treturn None\n",
    "\t\telse:\n",
    "\t\t\tleft, right = 0, len(nums) - 1\n",
    "\t\t\tmid = (left + (right - left) + 1) // 2\n",
    "\t\t\troot_node = TreeNode(nums[mid])\n",
    "\t\t\troot_node.left = self.sortedArrayToBST(nums[:mid])\n",
    "\t\t\troot_node.right = self.sortedArrayToBST(nums[mid + 1:])\n",
    "\t\t\treturn root_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left,right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            mid=(left+right)//2\n",
    "            root=TreeNode(nums[mid])\n",
    "            root.left=helper(left,mid-1)\n",
    "            root.right=helper(mid+1,right)\n",
    "            return root\n",
    "    \n",
    "        return helper(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "\n",
    "            # 总是选择中间位置左边的数字作为根节点\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid - 1)\n",
    "            root.right = helper(mid + 1, right)\n",
    "            return root\n",
    "\n",
    "        return helper(0, len(nums) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums: return\n",
    "\n",
    "        mid_idx = len(nums)//2\n",
    "        root = TreeNode(nums[mid_idx])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid_idx])\n",
    "        root.right = self.sortedArrayToBST(nums[mid_idx+1:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid=len(nums)//2\n",
    "        root=TreeNode(nums[mid])\n",
    "        root.left=self.sortedArrayToBST(nums[:mid])\n",
    "        root.right=self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        if len(nums)==1:\n",
    "            return TreeNode(nums[0])\n",
    "        i = len(nums)//2\n",
    "        node = TreeNode(nums[i])\n",
    "        if i>0:\n",
    "            node.left = self.sortedArrayToBST(nums[:i])\n",
    "        if i<len(nums)-1:\n",
    "            node.right = self.sortedArrayToBST(nums[i+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        nums.sort()\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return \n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[: mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid + 1: ])\n",
    "        \n",
    "        return root \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left,right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            mid = (left + right) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left , mid - 1)\n",
    "            root.right = helper(mid + 1 , right)\n",
    "            return root\n",
    "\n",
    "        return helper(0,len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return \n",
    "        mid = math.floor(len(nums) / 2)\n",
    "        node = TreeNode(nums[mid])\n",
    "        node.left = self.sortedArrayToBST(nums[0: mid])\n",
    "        node.right = self.sortedArrayToBST(nums[mid + 1: len(nums)])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        return self.createTreeNode(nums)\n",
    "\n",
    "    def createTreeNode(self, nums):\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        mid_pos = len(nums) // 2\n",
    "        node = TreeNode(nums[mid_pos])\n",
    "        node.left = self.createTreeNode(nums[0:mid_pos])\n",
    "        node.right = self.createTreeNode(nums[mid_pos+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "\n",
    "        index = len(nums) // 2\n",
    "        node = TreeNode(nums[index])\n",
    "        node.left = self.sortedArrayToBST(nums[0:index])\n",
    "        node.right = self.sortedArrayToBST(nums[index+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return \n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        if len(nums)==1:\n",
    "            return TreeNode(nums[0])\n",
    "        i=len(nums)//2\n",
    "        root=TreeNode(nums[i])\n",
    "        root.left=self.sortedArrayToBST(nums[:i])\n",
    "        root.right=self.sortedArrayToBST(nums[i+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def findroot(left,right):\n",
    "            if right<left:\n",
    "                return None\n",
    "            mid = int((left+right)/2)\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = findroot(left,mid-1)\n",
    "            root.right = findroot(mid+1,right)\n",
    "            return root\n",
    "        \n",
    "        root = findroot(0,len(nums)-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "\n",
    "            # 总是选择中间位置左边的数字作为根节点\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid - 1)\n",
    "            root.right = helper(mid + 1, right)\n",
    "            return root\n",
    "\n",
    "        return helper(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return\n",
    "            mid = (left + right)//2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid-1)\n",
    "            root.right = helper(mid+1, right)\n",
    "            return root\n",
    "        return helper(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        #别人的代码\n",
    "        def  build_root(left,right):\n",
    "            if left>right:\n",
    "                return None\n",
    "\n",
    "            #取中间位置左边的数字作为根节点\n",
    "            mid=(left+right)//2\n",
    "            root=TreeNode(nums[mid])\n",
    "\n",
    "            root.left=build_root(left,mid-1)\n",
    "            root.right=build_root(mid+1,right)\n",
    "\n",
    "            return root\n",
    "        return build_root(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        \n",
    "    \n",
    "        def func(nums, low, high):\n",
    "            if low > high: return\n",
    "            \n",
    "            mid = (high - low) // 2 + low\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = func(nums, low, mid - 1)\n",
    "            root.right = func(nums, mid + 1, high)\n",
    "            return root\n",
    "        return func(nums, 0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "\n",
    "        def travel(nums, left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            mid = (left + right) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = travel(nums, left, mid-1)\n",
    "            root.right = travel(nums, mid+1, right)\n",
    "            return root\n",
    "        \n",
    "        return travel(nums, 0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            mid = (left+right)//2\n",
    "            node = TreeNode(nums[mid])\n",
    "            node.left = helper(left, mid-1)\n",
    "            node.right = helper(mid+1, right)\n",
    "            return node \n",
    "        root = helper(0,len(nums)-1)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "\n",
    "            # 总是选择中间位置左边的数字作为根节点\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid - 1)\n",
    "            root.right = helper(mid + 1, right)\n",
    "            return root\n",
    "\n",
    "        return helper(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        # [left, right] 递归构建\n",
    "        def dfs(nums, left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            elif left == right:\n",
    "                return TreeNode(nums[left])\n",
    "            else:\n",
    "                mid = left + right >> 1\n",
    "                root = TreeNode(nums[mid])\n",
    "                root.left = dfs(nums, left, mid-1)\n",
    "                root.right = dfs(nums, mid+1, right)\n",
    "                return root\n",
    "        \n",
    "        return dfs(nums, 0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        mid = len(nums)//2\n",
    "        l1 = nums[:mid]\n",
    "        l2 = nums[mid+1:]\n",
    "        head = TreeNode(nums[mid])\n",
    "        head.left = self.sortedArrayToBST(l1)\n",
    "        head.right = self.sortedArrayToBST(l2)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        # [-10,-3,0,5,9]\n",
    "        def build(nums, l, r):\n",
    "            if l > r: return None\n",
    "            if l == r:\n",
    "                return TreeNode(nums[l])\n",
    "            m = (l + r) // 2\n",
    "            node = TreeNode(nums[m])\n",
    "            node.left = build(nums, l, m - 1)\n",
    "            node.right = build(nums, m + 1, r)\n",
    "            return node\n",
    "\n",
    "        return build(nums, 0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return TreeNode(nums[i])\n",
    "\n",
    "            if i > j:\n",
    "                return None\n",
    "\n",
    "            mid = (i + j) // 2\n",
    "            temp = TreeNode(nums[mid])\n",
    "            temp.left = dfs(i, mid - 1)\n",
    "            temp.right = dfs(mid + 1, j)\n",
    "\n",
    "            return temp\n",
    "\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return  None \n",
    "\n",
    "        sep_idx = int(len(nums) / 2)\n",
    "        sep_val = nums[sep_idx]\n",
    "        \n",
    "        root = TreeNode(val=sep_val)\n",
    "        left_nums = nums[0: sep_idx]\n",
    "        right_nums = nums[sep_idx + 1: ]\n",
    "\n",
    "        root.left = self.sortedArrayToBST(left_nums)\n",
    "        root.right = self.sortedArrayToBST(right_nums)\n",
    "\n",
    "        return root \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        if len(nums) < 2:\n",
    "            return TreeNode(nums[0])\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid + 1:])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        mid = len(nums) // 2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "\n",
    "            # 总是选择中间位置左边的数字作为根节点\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid - 1)\n",
    "            root.right = helper(mid + 1, right)\n",
    "            return root\n",
    "\n",
    "        return helper(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        #确定左右边界\n",
    "        left, right = 0, len(nums) - 1\n",
    "        #递归建立树\n",
    "        def DFS(nums, left, right):\n",
    "            #终止条件，区间为空\n",
    "            if left > right:\n",
    "                return \n",
    "            #当前工作\n",
    "            mid = left + (right - left) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            #递推\n",
    "            root.left = DFS(nums, left, mid - 1)\n",
    "            root.right = DFS(nums, mid + 1, right)\n",
    "            #返回\n",
    "            return root\n",
    "\n",
    "        root = DFS(nums, left, right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "\n",
    "        n = len(nums)\n",
    "        center = n // 2\n",
    "        left = nums[:center]\n",
    "        right = nums[center + 1:]\n",
    "        root = TreeNode(nums[center])\n",
    "        root.left = self.sortedArrayToBST(left)\n",
    "        root.right = self.sortedArrayToBST(right)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return  None \n",
    "\n",
    "        sep_idx = int(len(nums) / 2)\n",
    "        sep_val = nums[sep_idx]\n",
    "        \n",
    "        root = TreeNode(val=sep_val)\n",
    "        left_nums = nums[0: sep_idx]\n",
    "        right_nums = nums[sep_idx + 1: ]\n",
    "\n",
    "        root.left = self.sortedArrayToBST(left_nums)\n",
    "        root.right = self.sortedArrayToBST(right_nums)\n",
    "\n",
    "        return root \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        idx = len(nums) // 2\n",
    "        root = TreeNode(nums[idx])\n",
    "        root.left = self.sortedArrayToBST(nums[:idx])\n",
    "        root.right = self.sortedArrayToBST(nums[idx + 1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        \n",
    "        def maketree(l,r):\n",
    "            if l>r:\n",
    "                return None\n",
    "            mid=(l+r)//2\n",
    "            tree_node=TreeNode(nums[mid])\n",
    "            tree_node.left=maketree(l,mid-1)\n",
    "            tree_node.right=maketree(mid+1,r)\n",
    "\n",
    "            return tree_node\n",
    "        \n",
    "        return maketree(0,len(nums)-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "\n",
    "        def build_tree(left, right):\n",
    "            if left > right:\n",
    "                return\n",
    "            # 中间位置左边数字\n",
    "            mid = left + (right - left) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = build_tree(left, mid - 1)\n",
    "            root.right = build_tree(mid + 1, right)\n",
    "            return root\n",
    "        return build_tree(0, len(nums) - 1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def helper(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = helper(left, mid - 1)\n",
    "            root.right = helper(mid + 1, right)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return helper(0, len(nums) - 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        def dfs(i: int, j: int) -> TreeNode:\n",
    "            if i > j:\n",
    "                return None\n",
    "            \n",
    "            if i == j:\n",
    "                return TreeNode(nums[i])\n",
    "            \n",
    "            mid = (i+j) // 2\n",
    "            node = TreeNode(nums[mid])\n",
    "\n",
    "            node.left = dfs(i, mid-1)\n",
    "            node.right = dfs(mid+1, j)\n",
    "\n",
    "            return node\n",
    "        \n",
    "        return dfs(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def dfs(nums):\n",
    "            if not nums: return\n",
    "            mid = len(nums) // 2\n",
    "            return TreeNode(nums[mid], dfs(nums[:mid]), dfs(nums[mid + 1:]))\n",
    "        return dfs(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        n = len(nums)\n",
    "        if n==0:return None\n",
    "        if n==1:return TreeNode(nums[0])\n",
    "        left = self.sortedArrayToBST(nums[:n//2])\n",
    "        right = self.sortedArrayToBST(nums[n//2+1:])\n",
    "        root = TreeNode(nums[n//2])\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        queue = []\n",
    "        self.inqueue(queue, nums)\n",
    "        return self.dequeue(queue)\n",
    "\n",
    "    def inqueue(self, queue, nums):\n",
    "        if len(nums) == 0:\n",
    "            queue.append(None)\n",
    "            return\n",
    "        mid_pos = len(nums) // 2\n",
    "        queue.append(nums[mid_pos])\n",
    "        self.inqueue(queue, nums[0:mid_pos])\n",
    "        self.inqueue(queue, nums[mid_pos+1:])\n",
    "\n",
    "    def dequeue(self, queue):\n",
    "        if len(queue) == 0:\n",
    "            return None\n",
    "        num = queue.pop(0)\n",
    "        if num is None:\n",
    "            return None\n",
    "        node = TreeNode(num)\n",
    "        node.left = self.dequeue(queue)\n",
    "        node.right = self.dequeue(queue)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        mid = len(nums)//2\n",
    "        root = TreeNode(nums[mid])\n",
    "        root.left = self.sortedArrayToBST(nums[:mid])\n",
    "        root.right = self.sortedArrayToBST(nums[mid+1:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return\n",
    "        root_index = len(nums) // 2\n",
    "        root = TreeNode(nums[root_index])\n",
    "        root.left = self.sortedArrayToBST(nums[:root_index])\n",
    "        root.right = self.sortedArrayToBST(nums[root_index + 1:])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        n = len(nums)//2\n",
    "        node = TreeNode(nums[n])\n",
    "        node.left = self.sortedArrayToBST(nums[:n])\n",
    "        node.right = self.sortedArrayToBST(nums[n+1:])\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "\n",
    "        def dfs(nums, left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            mid = (left+right)//2\n",
    "\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = dfs(nums, left, mid-1)\n",
    "            root.right = dfs(nums, mid+1, right)\n",
    "\n",
    "            return root\n",
    "\n",
    "        \n",
    "        return dfs(nums, 0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n",
    "        def dfs(left, right):\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            return TreeNode(nums[left+(right-left+1)//2], left = dfs(left, left+(right-left+1)//2-1), right = dfs(left+(right-left+1)//2+1, right))\n",
    "        \n",
    "        return dfs(0, len(nums)-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
